open Types
open Utils

exception NotAnException

(** {2 Fonctions de manipulation de flow} *)

(** [init p] retourne l'identifiant du point d'entrée du programme p
    @param p un programme
*)
let rec init (p) : int = match p with
  | Skip(l) -> l
  | Assign(_,_,l) -> l
  | Seq(s1, _) -> init s1
  | If(_,_,_,l) -> l
  | While(_,_,l) -> l
  | _ -> failwith "Unknown instr"

(** [final p] retourne la liste des identifiants des points d'entrée du programme p
    @param p un programme
*)
let rec final p : int list = match p with
  | Skip(l) -> l::[]
  | Assign(_,_,l) -> l::[]
  | Seq(_, s2) -> final s2
  | If(_,s1,s2,_) -> (final s1) @ (final s2)
  | While(_,_,l) -> l::[]
  | _ -> failwith "Unknown instr"

(** [labels p] retourne la liste des labels présents dans le programme 
    @param p un programme
*)
let rec labels p : int list = match p with
  | Skip(l) -> [l]
  | Assign(_,_,l) -> [l]
  | Seq(s1, s2) -> (labels s1) @ (labels s2)
  | If(_,s1,s2,l) -> l::((labels s1) @ (labels s2))
  | While(_,s,l) -> l::(labels s)
  | _ -> failwith "Unknown instr"

(** [flow p] retourne lees identifiants des instructions représentant le flow d'exécution du programme
    @param p un programme
*)
let rec flow p : (int*int) list = match p with
  | Skip(_) -> []
  | Assign(_) -> []
  | Seq(s1, s2) -> (complete_flow (init s2) (final s1)) @ (flow s1) @ (flow s2)
  | If(_, s1, s2, l) -> [(l, init s1); (l, init s2)] @ (flow s1) @ (flow s2)
  | While(_, s, l) ->  ((l, init s)::(flow s)) @ (complete_flow l (final s))
  | _ -> failwith "Unknown instr"

(** [complete_flow o inL] permet l'ajout de plusieurs chemin allant des labels contenu dans la liste inL vers le label o 
    @param o le noeud de sortie des chemins à créer
    @param inL la liste des noeuds d'entrée
*)
and complete_flow (o:int) (inL:int list) : (int*int) list =
  match inL with 
  | [] -> []
  | i::l -> (i, o)::(complete_flow o l)

(** [preds flw cur] permet la récupération de tous les labels des prédécesseurs d'un neud
    @param flw le flot dans lequel cherché
    @param cur le noeud courant dans lequel chercher
*)
let rec preds flw cur = 
  match flw with
  | [] -> []
  | (i,o)::flw' -> let p = preds flw' cur in if cur == o then i::p else p

(** [preds flw cur] permet la récupération de tous les labels des successeurs d'un neud
    @param flw le flot dans lequel cherché
    @param cur le noeud courant dans lequel chercher
*)
let rec succ flw cur = 
  match flw with 
  | [] -> []
  | (i,o)::flw' -> let s = succ flw' cur in if cur == i then o::s else s

(** [check_cycle lbls] vérifie si tous les noeuds ont été visités
    @param la liste totale des labels
    NOTE: utilisation d'une variable globale contenant la liste des labels visités
*)
let visited : int list ref = ref []

let rec check_cycle lbls = match lbls with
| [] -> true
| a::l -> try let _ = List.find (fun b -> a == b) !visited in check_cycle l
          with _ -> false

(** {2 Fonctions de manipulation de programme} *)

(** [get_vars expr] permet de récupérer la liste des variables uniques présentes dans une expression
    @param expr l'expression dans laquelle cherchée les variables
*)
let rec get_vars expr : var list = 
  uniq (get_vars_aux expr)
and get_vars_aux expr = match expr with
  | Expr_Num _ -> []
  | Expr_Bool _ -> []
  | Expr_Var v -> [v]
  | Expr_Neg e -> get_vars e
  | Expr_Plus (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Minus (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Mult (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Div (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Pow (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Equal (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Less (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_And (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Or (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Not e -> get_vars e
  | Expr_NotEqual (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_LessEqual (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_Greater (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | Expr_GreaterEqual (e1, e2) -> (get_vars e1) @ (get_vars e2)
  | _ -> failwith "Unknown expr"

(** [get_defs_var instr] permet la récupération de la liste des variables définies/modifiées dans une instruction
    @param instr
*)
let rec get_defs_var instr = match instr with
  | Assign(v,_,_) -> [v]
  | Seq(s1,s2) -> (get_defs_var s1) @ (get_defs_var s2)
  | _ -> []

(** [get_used_var instr] permet la récupération de la liste des variables utilisées dans une instruction
    @param instr
*)
let rec get_used_var instr = match instr with
| Assign(_, e, _) -> get_vars e
| If(c,_,_,_) -> get_vars c
| While(c,_,_) -> get_vars c
| Seq(s1,s2) -> (get_used_var s1) @ (get_used_var s2)
| _ -> []

(** [get_instr p l] permet la récupération d'une instruction via son label dans un programme
    @param p le programme
    @param l le label
*)
let rec get_instr p l = match p with
| Skip(l') -> if l == l' then p else raise NotAnException
| Assign(_,_,l') -> if l == l' then p else raise NotAnException
| Seq(s1, s2) -> begin
                  try 
                  let instr = get_instr s1 l in instr 
                 with NotAnException -> 
                  get_instr s2 l
                  end
| If(_,s1, s2, l') -> if l == l' then p else begin
                      try 
                        get_instr s1 l
                       with NotAnException -> 
                        get_instr s2 l
                      end
| While(_,s,l') -> if l == l' then p else get_instr s l
| _ -> failwith "Unknown instr"
